package com.heng.Demo.GetPrim;


import java.lang.String;

public class GetPrim {
    public static void main(String[] args) {
        System.out.println(merge(new int[]{1, 3,4,2,5}));
    }

    /**
        石子合并
     */
    static int merge(int[] nums) {
        int n = nums.length;
        int[][] dp = new int[n + 2][n + 2];
        int[] sum = new int[n + 1];
        for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + nums[i - 1];

        for (int len = 2; len <= n; len++) {
            for (int l = 1; l + len - 1 <= n; l++) {
                int r = l + len - 1;
                dp[l][r] = Integer.MAX_VALUE;
                for (int k = l; k < r; k++) {
                    int max = dp[l][k] + dp[k + 1][r] + sum[r] - sum[l - 1];
                    dp[l][r] = Math.min(dp[l][r] , max);
                }
            }
        }
        return dp[1][n];
    }
}
